package entity;

/**
 * @Author: wanqian
 * @Date: 2021/2/22 0:48
 */
public class BiSortTree {

    private BiSortNode root;

    public void add(BiSortNode node) {
        if (root == null) {
            this.root = node;
        } else {
            root.add(node);
        }

    }

    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        }
    }

    public BiSortNode search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    public BiSortNode searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    public void delNode(int value) {
        if (root == null) {
            return;
        }

        //查找目标节点
        BiSortNode node = search(value);
        if (node == null) {
            return;
        }
        //查找父节点
        BiSortNode parent = searchParent(value);
        //若为子节点
        if (node.getLeft() == null && node.getRight() == null) {
            if (parent == null) {
                root = null;
            } else if (parent.getLeft() != null && parent.getLeft().getValue() == value) {
                parent.setLeft(null);
            } else if (parent.getRight() != null && parent.getRight().getValue() == value) {
                parent.setRight(null);
            }
        } else if (node.getLeft() != null && node.getRight() != null) {
            //当目标节点有两个子节点
            int min = delRightTreeMin(node.getRight());
            node.setValue(min);
        } else {
            //当目标节点只有一个子节点
            if (node.getLeft() != null) {
                if (parent == null) {
                    root = node.getLeft();
                } else {
                    if (parent.getLeft() != null &&
                            parent.getLeft().getValue() == node.getValue()) {
                        parent.setLeft(node.getLeft());
                    } else {
                        parent.setRight(node.getLeft());
                    }
                }
            } else {
                if (parent == null) {
                    root = node.getRight();
                } else {
                    if (parent.getLeft() != null &&
                            parent.getLeft().getValue() == node.getValue()) {
                        parent.setLeft(node.getRight());
                    } else {
                        parent.setRight(node.getRight());
                    }
                }
            }
        }
    }

    /**
     * 找到并删除右侧最小节点
     *
     * @param node
     * @return
     */
    public int delRightTreeMin(BiSortNode node) {
        BiSortNode temp = node;
        while (temp.getLeft() != null) {
            temp = temp.getLeft();
        }
        delNode(temp.getValue());
        return temp.getValue();
    }

    /**
     * 找到并删除左侧最大数
     * @param node
     * @return
     */
    public int delLeftTreeMax(BiSortNode node) {
        BiSortNode temp = node;
        while (temp.getRight() != null) {
            temp = temp.getRight();
        }
        delNode(temp.getValue());
        return temp.getValue();
    }

    public BiSortTree(BiSortNode root) {
        this.root = root;
    }

    public BiSortNode getRoot() {
        return root;
    }

    public void setRoot(BiSortNode root) {
        this.root = root;
    }
}
